Bức tường được xây dựng trong sáu giai đoạn, khu vực phía sau bức tường được mở rộng từ một khu vực nhỏ gần Morocco ở phía bắc đến phần lớn phía tây và lấn dần vào trung tâm của lãnh thổ. Các bức tường được xây dựng là:

• Bức tường thứ 1 (tháng 8 năm 1980 - tháng 6 năm 1982) bao quanh "tam giác hữu ích" của El Aaiún, Smara và các mỏ phosphate ở Bou Craa (khoảng 500 km (310 dặm)).
• Bức tường thứ 2 (tháng 12 năm 1983 - tháng 1 năm 1984) bao quanh Amgala (khoảng 300 km (190 dặm)).
• Bức tường thứ 3 (tháng 4 năm 1984 - tháng 5 năm 1984) bao quanh Jdiriya và Haouza (khoảng 320 km (200 dặm)).
• Bức tường thứ 4 (tháng 12 năm 1984 - tháng 1 năm 1985) bao quanh Mahbes và Farciya (khoảng 380 km (240 dặm))
• Bức tường thứ 5 (từ tháng 5 đến tháng 9 năm 1985) bao quanh Guelta Zemmur, Bir Anzarane và Dakhla (khoảng 670 km (420 dặm))
• Bức tường thứ 6 (tháng 2 - tháng 4 năm 1987) bao quanh Auserd, Tichla và Bir Ganduz (550 km (340 dặm))